import java.util.*;
public class RespacePlus {
    class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        public TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    TrieNode root;

    // private void buildTrie(String[] dictionary) {
    //     root = new TrieNode();
    //     for (String word : dictionary) {
    //         TrieNode node = root;
    //         // 从单词的最后一个字符开始插入，这样便于正向查找
    //         for (int i = word.length() - 1; i >= 0; i--) {
    //             int index = word.charAt(i) - 'a';
    //             if (node.children[index] == null) {
    //                 node.children[index] = new TrieNode();
    //             }
    //             node = node.children[index];
    //         }
    //         node.isEnd = true;
    //     }
    // }

    // public int respace(String[] dictionary, String sentence) {
    //     buildTrie(dictionary);
    //     int n = sentence.length();
    //     int[] dp = new int[n + 1];
    //      for (int i = 1; i <= n; i++) {
    //         // 默认情况下，当前字符不能识别，继承前一个状态并加1
    //         dp[i] = dp[i - 1] + 1;
            
    //         // 从当前位置i向左查找可能的单词
    //         TrieNode node = root;
    //         for (int j = i - 1; j >= 0; j--) {
    //             int index = sentence.charAt(j) - 'a';
    //             // 如果当前字符不在字典树中，则停止查找
    //             if (node.children[index] == null) {
    //                 break;
    //             }
                
    //             node = node.children[index];
    //             // 如果找到一个完整的单词
    //             if (node.isEnd) {
    //                 dp[i] = Math.min(dp[i], dp[j]);
    //             }
    //             // 即使没找到完整单词，也继续检查，因为可能有更长的单词
    //         }
    //     }
    //     return dp[n];
    // }

    private void buildTrie(String[] dictionary) {
        root = new TrieNode(); // 确保初始化root
        for(String word : dictionary){
           TrieNode node = root;
           for(char c : word.toCharArray()){  // 正向插入
              int index = c - 'a';
              if(node.children[index] == null){
                node.children[index] = new TrieNode();
              }
              node = node.children[index];
           }
           node.isEnd = true;  // 标记单词结束
        }
    }
    
    public int respace(String[] dictionary, String sentence) {
        buildTrie(dictionary);
        int n = sentence.length();
        int[] dp = new int[n+1];
        for(int i = 1; i<=n; i++){
          dp[i] = dp[i-1] + 1;  // 默认情况：当前字符不匹配，未识别字符+1
          TrieNode node = root;
          for(int j = i-1; j>=0; j--){  // 从当前位置向左查找
             int index = sentence.charAt(j) - 'a';
             if(node.children[index] == null){
              dp[i] = Math.min(dp[j] + i - j, dp[i]);
               break;  // 无法继续匹配，跳出循环
             }
             node = node.children[index];
             if(node.isEnd){  // 修复：检查当前节点是否为单词结束
               dp[i] = Math.min(dp[j] + i - j, dp[i]);
             }
             // 注意：即使没找到完整单词也继续，因为可能有更长的匹配
          }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        String[] dictionary = {"looked","just","like","her","brother"};
        String sentence = "jesslookedjustliketimherbrother";
        RespacePlus res = new RespacePlus();
        int result = res.respace(dictionary, sentence);
        System.out.println(result);  // 应该输出7
    }
}
